%Dowód NP-zupełności problemu

\begin{description}
\item[Twierdzenie.] Zdecydowanie, czy z danej planszy SameGame można usunąć wszystkie klocki jest NP-zupełne, jeśli plansza ma co najmniej dwie kolumny i co najmniej 5 kolorów.
\end{description}

Dowód przeprowadzony zostanie poprzez redukcję do problemu 3-Partition.  Dowód jego NP-zupełności znajduje się w \cite{3-partition-np-com}

\begin{description}
\item[Problem 3-Partition.] Dany jest multizbiór $A=\{a_{1}, a_{2},\cdots, a_{n}\}$ n = 3m całkowitych dodatnich liczb ograniczonych ustalonym wielomianem stopnia n, spełniających warunki $\sum_{i=1}^n a_{i} = tm$ oraz $\forall a \in A \colon \frac{t}{2} < a < \frac{t}{4}$. Czy istnieje podział zbioru A na podzbiory $S_{1},S_{2},\cdots, S_{m}$ taki, że $\forall i \sum_{a \in S_{i}} a = t$?
\end{description}

\section{Konstrukcja}
Problem SameGame którego równoważność wykażemy posiada dwie kolumny; poglądowy wygląd konstrukcji przedstawia rysunek ~\ref{fig:constr}. 

W prawej kolumnie znajdują się bloki zielonych klocków kodujące liczby zbioru A, zaczynając od dołu. Blok dla liczby a ma wysokość 4ma. Każde dwa sąsiadujące zielone bloki oddzielone są pojedynczym niebieskim klockiem, sumaryczna wysokość tego fragmentu konstrukcji wynosi więc $4m^{2}t + 3m - 1$. Powyżej zielono-niebieskiego bloku znajdują się czerwone klocki których usunięcie będziemy utożsamiac z poprawnym przyporządkowaniem trzech liczb o sumie t do jednego ze zbiorów. Czerwonych klocków jest m-1, a każde dwa oddzielone sa parą niebieskich klocków - separatorów. Wysokość tego fragmentu wynosi więc 3m - 5.

Lewa kolumna, od dołu, rozpoczyna się od bloku 3m czarnych i bialych klocków, dla ustalenia uwagi zaczynając od czarnego klocka. W całej lewej kolumnie klocki czarne i białe ulożone są naprzemiennie, żadne dwa czarne i żadne dwa biale klocki nie sąsiaduja ze sobą w początkowej pozycji. Następnie znajduje się m-1 sekcji odpowiadających kolejnym zbiorom. Każda z sekcji ma wysokość 4mt i zawiera same czarne i białe klocki, oraz pojedynczy czerwony klocek na szczycie. Dodatkowo, jeśli na pewnej wysokosci h znajduje sie czerwony klocek, to klocki na wysokościach h-1 i h+1 mają różne kolory, tzn. naprzemiennosc klocków czarnych i bialych zostaje zachowana nawet po usunięciu pojedynczych czerwonych klocków. Ostatnim blokiem lewej kolumny jest ponownie blok naprzemiennie czarnych i bialych klockow. Klocków tych jest tyle, co wszystkich czarnych i bialych poniżej a więc $4m^{2}t - 4mt + 2m + 1$. Blok ten zaczyna sie klockiem takiego koloru, jakim skończyl się ostatni blok sekcji niżej, tzn. jeden raz nie jest zachowana naprzemienność z pominięciem czerwonych klocków. Powoduje to, że w stanie początkowym żaden biały ani czarny klocek nie może zostać usunięty, jednak usunięcie wszystkich czerwonych klocków pozwala łatwo usunąć całą lewą kolumnę.

Konstrukcja na rysunku nie zachowuje skali, co najważniejsze - w rzeczywistości klocki czerwone w prawej kolumnie znajdują się wyżej od najwyższego czerwonego klocka lewej kolumny. Różnica wysokości pomiędzy najwyższym czerwonym klockiem w lewej kolumnie a najniższym czerwonym klockiem w prawej kolumnie wynosi 4mt.

\begin{figure}
	\centering
	\includegraphics[width=0.70\textwidth]{../src/img/konstrukcja.png}
	\caption{Konstrukcja poglądowa.}
	\label{fig:constr}
\end{figure}

\section{Dowód - część pierwsza}
Niech $S_{1}, S_{2}, \cdots , S_{m}$ będzie rozwiązaniem problemu 3-Partition, tzn. $S_{k} = \{a_{k}, b_{k}, c_{k}\}, \forall k \colon a_{k} + b_{k} + c_{k} = t$. Dodatkowo kolejność zbiorów $S_{k}$ organizujemy tak, aby liczba $a_{n}$ trafiła do zbioru $S_{m}$. Dla każdego ze zbiorów $S_{k}$ wykonujemy następujące 5 ruchów:

\begin{enumerate}
	\item Usuwamy blok zielonych klocków skojarzonych z liczbą $a_{k}$
	\item Usuwamy blok zielonych klocków skojarzonych z liczbą $b_{k}$
	\item Usuwamy blok zielonych klocków skojarzonych z liczbą $c_{k}$
	\item Usuwamy parę czerwonych klocków
	\item Usuwamy najniższy niebieski separator
\end{enumerate}

Pierwsze trzy ruchy zawsze są możliwe do wykonania. Ponieważ $a_{k} + b_{k} + c_{k} = t$ więc suma usuniętych klocków to 4mt. Tyle wlaśnie wynosi różnica wysokości między czerwonymi klockami, co pozwala nam wykonać ruch nr. 4. Ruch 5 przesuwa kolejny czerwony klocek tak, aby był dokładnie 4mt klocków wyżej od odpowiadającego mu czerwonego klocka lewej kolumny.

Usunęliśmy w ten sposób wszystkie czerwone klocki. Pozostały 3 zielone grupy które możemy usunąć, separatory zielonych grup stanowią teraz jeden blok który możemy usunąć, a cala lewa kolumna zgodnie z jej konstrukcją bez czerwonych klocków zredukuje się do zera. Pokazaliśmy więc, że jeśli problem 3-Partition posiada rozwiązanie, to odpowiadający mu problem SameGame posiada rozwiązanie.

\section{Dowód - część druga}

Załóżmy, że egzemplarz problemu SameGame posiada rozwiązanie, tzn. istnieje pewna sekwencja ruchów po ktorej plansza jest pusta.

Pokażemy, że każde rozwiązanie usuwa czerwone klocki z lewej kolumny w kolejności od góry do dołu. Załóżmy wbrew tezie, że istnieje rozwiązanie które usuwa czerwone klocki z lewej kolumny poza kolejnością. Oznacza to jednak, że w pewnym momencie usuwamy czerwony klocek z lewej kolumny, gdy 4mt pozycji wyżej znajduje się jeszcze inny czerwony klocek. Tymczasem najwyższy czerwony klocek w prawej kolumnie nie moze leżeć wyżej niż 3m-5 pozycji wyżej. W lewej kolumnie znajduje się więc czerwony klocek który leży wyżej niż każdy z czerwonych klocków w prawej kolumnie. Ruchy które możemy wykonywać jedynie obniżaja czerwone klocki w prawej kolumnie nie zmieniając lewej, lub obniżaja obie kolumny o 1. Różnica wysokości nigdy nie maleje, a więc czerwony klocek z lewej kolumny nigdy nie zostanie usunięty. Ta sprzeczność dowodzi konieczności usuwania czerwonych klockow od góry w każdym poprawnym rozwiązaniu.

Zauważmy, że usuwanie czarnych i białych klocków tak na prawdę nie wpływa na stan rozwiązania - zawsze usuwamy dwa odpowiadajace sobie klocki, nigdy nie zmieniamy wysokosci czerwonych klockow w lewym rzędzie. Możemy więc rozważać tylko sekwencje w których czarne i białe klocki usuwane są na samym końcu i nigdy wcześniej nie tracąc ogólności.

Usunięcie separatora czerwonych klocków z prawej kolumny kiedy po obu jego stronach znajduje się jeszcze czerwony klocek uniemożliwia rozwiązanie. Dzieje sie tak ponieważ klocki z lewej kolumny nigdy nie zmieniają swojej wysokości i muszą być usuwane przy pomocy odpowiadających im klocków z prawej kolumny. W obu kolumnach czerwonych klockow jest dokładnie tyle samo, jeśli więc kiedykolwiek dwa czerwone klocki w prawej kolumnie zetkną się, operacja usunięcia czerwonych klocków usunie więcej niż jeden klocek z prawej kolumny, i tylko jeden klocek z lewej kolumny, a więc zabraknie klocka odpowiadającego jednemu z pozostałych w lewej kolumnie czerwonych klocków.

Oznacza to, że jedynymi ruchami jakimi może zaczynać się poprawne rozwiązanie jest usuwanie zielonych grup, po czym usunięcie pary czerwonych klocków. Oznacza to, ze musimy z prawej kolumny usunac $4mt + 3k, k \in {0, 1, \cdots, m-2}$ klocków aby wyrównać wysokość najwyższego klocka lewej kolumny z pewnym czerwonym klockiem prawej kolumny.

Jeśli usuniemy grupy odpowiadajace liczbom sumujacym sie do t' > t, to usuniemy co najmniej 4mt + 4m klocków. Jednak 4m > 3m - 5, a więc najwyższy czerwony klocek w prawej kolumnie znajdzie się niżej niż pewien czerwony klocek z lewej kolumny, co jak już pokazaliśmy jest sprzeczne z założeniem że rozwiązanie jest poprawne.

Jeśli usuniemy grupy odpowiadające liczbom sumującym sie do t' < t, to usuniemy co najwyżej 4mt - 4m klocków. Separatorów grup zielonych jest nie wiecej niż m-1, a więc nawet usuwając je wszystkie nie obniżymy wystarczajaco nawet najniższego czerwonego klocka.

Musimy więc usunąć liczby sumujące się dokładnie do t aby rozwiązanie było poprawne. Z warunku problemu 3-Partition $\forall a \in A \colon \frac{t}{2} < a < \frac{t}{4}$ wynika, że grup tych musiało być dokładnie 3. Rozumowanie to powtarzamy dla każdego kolejnego czerwonego klocka, dostajemy wiec m-1 trzyelementowych zbiorów liczb ze zbioru A, z których każdy sumuje się do t. Pozostałe liczby również sumują się do t, pokazaliśmy więc że jeśli Problem SameGame ma rozwiazanie, to ma też rozwiązanie odpowiadający mu problem 3-Partition.

Udowodniliśmy zatem równoważność obu problemów, co kończy dowód NP-zupełności problemu SameGame w przypadku 2 kolumn i 5 kolorów.

\section{Rozszerzenie na więcej kolumn/więcej kolorów}
Rozszerzenie powyższego dowodu jest bardzo proste. Dodatkowe kolumny wypełniamy w całosci kolorem bialym lub czarnym (nieistotne) i powyższy dowód pozostaje w mocy. Wiecej kolorów możemy uzyskać dodając w lewej kolumnie pary klocków tego samego koloru ponad sekcjami opisanymi w powyższej konstrukcji, ponownie nie wpływajac na dowód NP-zupełności.

\section{Trudność problemu minimalizacji}
Załóżmy, że posiadamy algorytm rozwiązujący problem minimalizacji ilości pozstałych klocków dla danej planszy. Jeśli liczba ta wynosi 0, to problem jest rozwiązywalny, a jeśli jest większa - nie. Korzystając z tego algorytmu możemy więc rozwiązać problem NP-zupełny, a więc problem minimalizacji jest co najmniej tak samo trudny.
